By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 31, Issue 5, pp. 1315-1643

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Recognizing Dart-Free Perfect Graphs

V. Chvátal, J. Fonlupt, L. Sun, and A. Zemirline

pp. 1315-1338

BibTeX  Abstract Full Text:  PDF

Algorithms for a Minimum Volume Enclosing Simplex in Three Dimensions

Yunhong Zhou and Subhash Suri

pp. 1339-1357

BibTeX  Abstract Full Text:  PDF

Perceptron, Winnow, and PAC Learning

Rocco A. Servedio

pp. 1358-1369

BibTeX  Abstract Full Text:  PDF

Minimizing the Flow Time Without Migration

Baruch Awerbuch, Yossi Azar, Stefano Leonardi, and Oded Regev

pp. 1370-1382

BibTeX  Abstract Full Text:  PDF

Pseudorandom Functions and Factoring

Moni Naor, Omer Reingold, and Alon Rosen

pp. 1383-1404

BibTeX  Abstract Full Text:  PDF

Generators of $H_1(\Gamma_{h},\mathbbZ)$ for Triangulated Surfaces: Construction and Classification

R. Hiptmair and J. Ostrowski

pp. 1405-1423

BibTeX  Abstract Full Text:  PDF

A Theorem on Sensitivity and Applications in Private Computation

Anna Gál and Adi Rosén

pp. 1424-1437

BibTeX  Abstract Full Text:  PDF

A Linear Algorithm for Finding the Invariant Edges of an Edge-Weighted Graph

F. M. Malvestuto and M. Mezzini

pp. 1438-1455

BibTeX  Abstract Full Text:  PDF

Characterizations of 1-Way Quantum Finite Automata

Alex Brodsky and Nicholas Pippenger

pp. 1456-1478

BibTeX  Abstract Full Text:  PDF

Fast Greedy Algorithms for Constructing Sparse Geometric Spanners

Joachim Gudmundsson, Christos Levcopoulos, and Giri Narasimhan

pp. 1479-1500

BibTeX  Abstract Full Text:  PDF

Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

Adam R. Klivans and Dieter van Melkebeek

pp. 1501-1526

BibTeX  Abstract Full Text:  PDF

On Counting Independent Sets in Sparse Graphs

Martin Dyer, Alan Frieze, and Mark Jerrum

pp. 1527-1541

BibTeX  Abstract Full Text:  PDF

Safe Weak Minimization Revisited

Dieter Spreen

pp. 1542-1556

BibTeX  Abstract Full Text:  PDF

Testing Membership in Languages that Have Small Width Branching Programs

Ilan Newman

pp. 1557-1570

BibTeX  Abstract Full Text:  PDF

Self-Stabilizing Symmetry Breaking in Constant Space

Alain Mayer, Rafail Ostrovsky, Yoram Ofek, and Moti Yung

pp. 1571-1595

BibTeX  Abstract Full Text:  PDF

Approximating the Longest Cycle Problem in Sparse Graphs

Tomás Feder, Rajeev Motwani, and Carlos Subi

pp. 1596-1607

BibTeX  Abstract Full Text:  PDF

Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs

Eran Halperin

pp. 1608-1623

BibTeX  Abstract Full Text:  PDF

Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities

E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan, and K. Makino

pp. 1624-1643

BibTeX  Abstract Full Text:  PDF